package code138;

import java.util.HashMap;
import java.util.Map;

public class Code138 {

    public Node copyRandomList(Node head) {
        if(head==null)
            return null;
        Map<Node,Node> map = new HashMap<>();
        for (Node x = head;x!=null;x=x.next){
            Node node = new Node(x.val);
            map.put(x,node);
        }
        for (Node x = head;x!=null;x=x.next){
            map.get(x).next = map.get(x.next);
            map.get(x).random = map.get(x.random);
        }
        return map.get(head);
    }
}
